package com.sx.sx1.lintcode.day717;

import java.util.*;
import java.util.ArrayList;
import java.util.Stack;

public class LC595 {


    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }


    static class Solution {
        /**
         * @param root: the root of binary tree
         * @return: the length of the longest consecutive sequence path
         */
        public int longestConsecutive(TreeNode root) {
            Stack<TreeNode> s = new Stack<>();
            TreeNode  pre =null;
            List<Integer> path = new ArrayList<>();
            int[] ans = {0};
            while (!s.isEmpty() || root!=null){
                while (root!=null){
                    path.add(root.val);
                    s.add(root);
                    root= root.left;
                }

                root = s.peek();
                if(root.left ==null && root.right ==null){
                    f(path,ans);
                }

                if(root.right ==null || root.right == pre){
                    root = s.pop();
                    path.remove(path.size()-1);
                    pre =root;
                    root =null;
                }else{
                    root =root.right;
                }
            }
            return ans[0];
        }
        public void f(List<Integer> ll,int[] ans){
            int n= ll.size();
            int[] dp = new int[n];
            Arrays.fill(dp,1);
            for (int i = 1; i <n ; i++) {
                if(ll.get(i)==ll.get(i-1)+1){
                    dp[i]=dp[i-1]+1;
                }
                ans[0] = Math.max(ans[0],dp[i]);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode t = new TreeNode(1);
        t.right = new TreeNode(3);
        t.right.left = new TreeNode(2);
        t.right.right = new TreeNode(4);
        t.right.right.right = new TreeNode(5);
        System.out.println(new Solution().longestConsecutive(t));
    }

}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
595 · 二叉树最长连续序列
算法
简单
通过率
43%

题目
题解35
笔记
讨论99+
排名
记录
描述
给一棵二叉树，找到最长连续路径的长度。
这条路径是指 任何的节点序列中的起始节点到树中的任一节点都必须遵循 父-子 联系。最长的连续路径必须是从父亲节点到孩子节点（不能逆序）。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例1:

输入:
{1,#,3,2,4,#,#,#,5}
输出:3
说明:
这棵树如图所示
   1
    \
     3
    / \
   2   4
        \
         5
最长连续序列是3-4-5，所以返回3.
样例2:

输入:
{2,#,3,2,#,1,#}
输出:2
说明:
这棵树如图所示：
   2
    \
     3
    /
   2
  /
 1
最长连续序列是2-3，而不是3-2-1，所以返回2.
标签
企业
网易
Google
相关题目

124
最长连续序列
中等

596
最小子树
简单

619
二叉树的最长连续子序列III
中等

614
二叉树的最长连续子序列 II
中等

717
二叉树具有相同值的最长路径
中等
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
43/133
已开启智能提示
发起考试
15 分 00 秒
123456789101112131415161718192021
}
控制台
历史提交

 */